﻿using System.Collections.Generic;
using Lists = Algoritmia.DataStructures.Lists;
using System.Linq;
using Algoritmia.StateSpaces;
using Algoritmia.Schemes;

namespace Algoritmia.Problems.ExactCover
{
    public class ExactCoverStateSpace : IReversibleForwardStateSpace<ExactCoverStateSpace.State,bool>
    {
        private readonly bool[][] _matrix;
        private readonly int _n;
        private readonly int _m;

        public class State
        {
            public State(int m)
            {
                Index = 0;
                Covered = new bool[m];
            }

            public bool[] Covered
            {
                get;
                private set;
            }

            public int Index
            {
                get;
                set;
            }
        }

        public ExactCoverStateSpace(bool[][]matrix)
        {
            _matrix = matrix;
             _n = matrix.Length;
            _m = matrix[0].Length;
        }

        #region Implementation of IForwardStateSpace<State,bool>

        public State Decide(State state, bool decision)
        {
            if (decision)
            {
                for (int j = 0; j < _m; j++)
                {
                    if (_matrix[state.Index][j])
                        state.Covered[j] = true;
                }
            }
            state.Index++;
            return state;
        }

        public IEnumerable<bool> Decisions(State state)
        {
            if ( state.Index < _n)
            {
                if (  !(from j in Enumerable.Range(0,_m) 
                       select _matrix[state.Index][j] && state.Covered[j]).Any(e => e) )
                {
                    yield return true;
                }
                yield return false;
            }
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_m); }
        }

        public bool IsFinal(State state)
        {
            return state.Index == _m && state.Covered.All(e => e);
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,bool>

        public State Undo(State state, bool decision)
        {
            state.Index--;
            if ( decision )
            {
                for(int j = 0; j < _m; j++)
                {
                    if (_matrix[state.Index][j])
                    {
                        state.Covered[j] = false;
                    }
                }
            }
            return state;
        }

        #endregion
    }

    public class ExactCoverSolver
    {
        private readonly BacktrackingEnumerator<ExactCoverStateSpace.State, bool, Lists.IList<bool>> _solver;

        public ExactCoverSolver()
        {
            _solver =
                new BacktrackingEnumerator<ExactCoverStateSpace.State, bool, Lists.IList<bool>>(
                    createSolution: (space, i, d, f) => d);
        }

        public Lists.IList<bool> Solve(bool[][]matrix)
        {
            return _solver.First(new ExactCoverStateSpace(matrix));
        }
    }
}
